/**
 * 剑指 Offer 07. 重建二叉树
 * https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 */
const {
  TreeNode,
  displayTreeNode,
} = require('../../libs/public');

let preBegin = 0;

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @param {number} inBegin
 * @param {number} inEnd
 * @return {TreeNode}
 */
function dfs(preorder, inorder, inBegin, inEnd) {
  if (inBegin > inEnd) {
    return null;
  }
  if (preBegin >= preorder.length) {
    return null;
  }
  const index = inorder.indexOf(preorder[preBegin], inBegin);
  const node = new TreeNode(preorder[preBegin]);
  preBegin += 1;
  node.left = dfs(preorder, inorder, inBegin, index - 1);
  node.right = dfs(preorder, inorder, index + 1, inEnd);
  return node;
}

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
  if (preorder.length <= 0) {
    return null;
  }
  preBegin = 0;
  return dfs(preorder, inorder, 0, inorder.length - 1);
}

console.log(displayTreeNode(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])) === '[3,9,20,null,null,15,7]');
console.log(displayTreeNode(buildTree([-1], [-1])) === '[-1]');
